﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Gunningine
{
    /// <summary>
    /// This is an acceleration structure used to speed up checks on entities, for instance:
    /// - what is the nearest entity to a point in space?
    /// - where are the most entities within a particular radius?
    /// </summary>
    internal class EntityGrid
    {
        /// <summary>
        /// Cell
        /// </summary>
        internal class Cell : IQuadtreeItem
        {
            private HashSet<Entity> entities = null;

            public HashSet<Entity> Entities
            {
                get { return this.entities; }
            }

            /// <summary>
            /// bounding area.
            /// </summary>
            private Vector3 boundsMin, boundsMax;

            /// <summary>
            /// Constructor.
            /// </summary>
            public Cell(Vector3 boundsMin, Vector3 boundsMax)
            {
                this.entities = new HashSet<Entity>();
                this.boundsMin = boundsMin;
                this.boundsMax = boundsMax;
            }

            /// <summary>
            /// Add an entity.
            /// </summary>
            /// <param name="entity"></param>
            public void AddEntity(Entity entity)
            {
                this.entities.Add(entity);
            }

            /// <summary>
            /// Remove an entity.
            /// </summary>
            /// <param name="entity"></param>
            public void RemoveEntity(Entity entity)
            {
                this.entities.Remove(entity);
            }

            #region IQuadtreeItem implementation

            public Vector3 BoundsMin
            {
                get { return this.boundsMin; }
            }

            public Vector3 BoundsMax
            {
                get { return this.boundsMax; }
            }

            #endregion
        }

        public float GridSizeX { get; private set; }

        public float GridSizeY { get; private set; }

        public int CellsX { get; private set; }

        public int CellsY { get; private set; }

        private Cell[] cells = null;

        public float MinExtentX
        {
            get { return 0.0f; }
        }

        public float MaxExtentX
        {
            get { return this.GridSizeX * this.CellsX; }
        }

        public float MinExtentY
        {
            get { return 0.0f; }
        }

        public float MaxExtentY
        {
            get { return this.GridSizeY * this.CellsY; }
        }

        private Quadtree tree = null;

        /// <summary>
        /// Constructor.
        /// </summary>
        /// <param name="worldMinX">minimum x-coord of world.</param>
        /// <param name="worldMinY">minimum y-coord of world.</param>
        /// <param name="worldMaxX">maximum x-coord of world.</param>
        /// <param name="worldMaxY">maximum y-coord of world.</param>
        /// <param name="worldMaxY">number of cells in x dimension.</param>
        /// <param name="worldMaxY">number of cells in y dimension.</param>
        public EntityGrid(float worldMinX, float worldMinY, float worldMaxX, float worldMaxY, int cellsX, int cellsY)
        {
            this.CellsX = cellsX;
            this.CellsY = cellsY;

            float worldSizeX = worldMaxX - worldMinX;
            float worldSizeY = worldMaxY - worldMinY;

            this.GridSizeX = worldSizeX / this.CellsX;
            this.GridSizeY = worldSizeY / this.CellsY;

            this.cells = new Cell[this.CellsX * this.CellsY];

            int index = 0;
            for (int y = 0; y < cellsY; ++y)
            {
                for (int x = 0; x < cellsX; ++x)
                {
                    Vector3 boundsMin = new Vector3(x * this.GridSizeX, y * this.GridSizeY, 0);
                    Vector3 boundsMax = new Vector3((x + 1) * this.GridSizeX, (y + 1) * this.GridSizeY, 512);

                    this.cells[index] = new Cell(boundsMin, boundsMax);
                    index++;
                }
            }

            // Build quad tree
            this.tree = new Quadtree(this.cells, 9, 8);
        }

        /// <summary>
        /// Add entity to grid.
        /// </summary>
        /// <param name="entity">entity</param>
        public void AddEntity(Entity entity)
        {
            int cellX = (int)(entity.Position.X / this.GridSizeX);
            int cellY = (int)(entity.Position.Y / this.GridSizeY);

            this.cells[cellX + cellY * this.CellsX].AddEntity(entity);
        }

        /// <summary>
        /// Remove entity from grid.
        /// </summary>
        /// <param name="entity">entity</param>
        public void RemoveEntity(Entity entity)
        {
            int cellX = (int)(entity.Position.X / this.GridSizeX);
            int cellY = (int)(entity.Position.Y / this.GridSizeY);

            this.cells[cellX + cellY * this.CellsX].RemoveEntity(entity);
        }

        /// <summary>
        /// Get entities in the cell that contains the given point.
        /// </summary>
        /// <param name="position">position.</param>
        /// <returns></returns>
        public HashSet<Entity> GetEntitiesInCell(Vector3 position)
        {
            int cellX = (int)(position.X / this.GridSizeX);
            int cellY = (int)(position.Y / this.GridSizeY);

            return this.cells[cellX + cellY * this.CellsX].Entities;
        }

        /// <summary>
        /// Get all entities in viewing frustum.
        /// </summary>
        /// <param name="renderSystem"></param>
        /// <param name="camera"></param>
        /// <returns></returns>
        public List<Entity> GetEntitiesInFrustum(RenderSystem renderSystem, Camera camera)
        {
            List<IQuadtreeItem> cellsInView = this.tree.GetItemsInFrustum(renderSystem, camera);
            List<Entity> entities = new List<Entity>();

            foreach (var cell in cellsInView)
            {
                Cell c = (Cell)cell;
                entities.AddRange(c.Entities);
            }

            return entities;
        }

        /// <summary>
        /// Gets entities within the specified radius.
        /// </summary>
        /// <param name="position"></param>
        /// <param name="radius"></param>
        /// <returns></returns>
        public List<Entity> GetEntitiesWithinRadius(Vector3 position, float radius, Entity exclude = null)
        {
            List<Entity> returnedEntities = new List<Entity>();

            // First, see how many cells we need to check (based on radius).
            int cx0 = (int)((position.X - radius) / this.GridSizeX);
            int cy0 = (int)((position.Y - radius) / this.GridSizeY);
            int cx1 = (int)((position.X + radius) / this.GridSizeX);
            int cy1 = (int)((position.Y + radius) / this.GridSizeY);

            if (cx0 < 0) cx0 = 0;
            if (cx0 >= this.CellsX) cx0 = this.CellsX - 1;
            if (cy0 < 0) cy0 = 0;
            if (cy0 >= this.CellsY) cy0 = this.CellsY - 1;
            if (cx1 < 0) cx1 = 0;
            if (cx1 >= this.CellsX) cx1 = this.CellsX - 1;
            if (cy1 < 0) cy1 = 0;
            if (cy1 >= this.CellsY) cy1 = this.CellsY - 1;

            float distSQ = radius * radius;
            for (int x = cx0; x <= cx1; ++x)
            {
                for (int y = cy0; y <= cy1; ++y)
                {
                    foreach (var entity in this.cells[x + y * this.CellsX].Entities)
                    {
                        if (entity.Position.SquaredDistance(position) < distSQ && entity != exclude)
                            returnedEntities.Add(entity);
                    }
                }
            }

            return returnedEntities;
        }

        /// <summary>
        /// Move entity to new position.
        /// </summary>
        /// <param name="entity">entity.</param>
        /// <param name="newPosition">new position.</param>
        public void MoveEntity(Entity entity, Vector3 newPosition)
        {
            int curCellX = (int)(entity.Position.X / this.GridSizeX);
            int curCellY = (int)(entity.Position.Y / this.GridSizeY);
            int newCellX = (int)(newPosition.X / this.GridSizeX);
            int newCellY = (int)(newPosition.Y / this.GridSizeY);

            if (curCellX != newCellX || curCellY != newCellY)
            {
                this.cells[curCellX + curCellY * this.CellsX].RemoveEntity(entity);
                this.cells[newCellX + newCellY * this.CellsX].AddEntity(entity);
            }
        }
    }
}
